/*
 rope - The C++ string algorithm library

 Copyright (C) 2008 Woojong Koh (jstrane@gmail.com)

 This program is free software; you can redistribute it and/or modify
 it under the terms of the GNU General Public License as published by
 the Free Software Foundation; either version 2 of the License, or
 (at your option) any later version.

 This program is distributed in the hope that it will be useful,
 but WITHOUT ANY WARRANTY; without even the implied warranty of
 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 GNU General Public License for more details.

 You should have received a copy of the GNU General Public License along
 with this program; if not, write to the Free Software Foundation, Inc.,
 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.

 Project page : http://code.google.com/p/rope 
*/
#ifndef AHO_CORASICK_H
#define AHO_CORASICK_H

#include <iostream>
#include <string>
#include <stdexcept>

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/visitors.hpp>
#include <boost/graph/breadth_first_search.hpp>

#define USE_HASH 0

#if USE_HASH
#	include <boost/functional/hash.hpp>
#	include <tr1/unordered_map>
#	include <tr1/unordered_set>
#	define MAP std::tr1::unordered_map
#	define SET std::set 				// unordered_set is inefficient.
#	define PAIR_HASH(x, y) , boost::hash<std::pair< x , y > >
#else
#	include <map>
#	define MAP std::map
#	define SET std::set
#	define PAIR_HASH(x, y) 
#endif

#include <iterator>

using namespace boost;

template<class T = std::string>
class aho_corasick
{
	public:
		friend class ac_constructor;

		typedef T string_t;
		typedef typename T::value_type char_t;
		typedef typename string_t::const_iterator str_cont_iter;

		typedef std::list<string_t> out_list_t;
		typedef boost::adjacency_list<vecS, vecS, directedS,
				property<vertex_name_t, out_list_t>,
				property<edge_name_t, char_t> > Graph;

		typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
		typedef typename graph_traits<Graph>::edge_descriptor Edge;
		typedef typename graph_traits<Graph>::out_edge_iterator out_edge_iterator;

		typedef typename property_map<Graph, edge_name_t>::type char_map_t;
		typedef typename property_map<Graph, vertex_name_t>::type out_map_t;

		typedef MAP<std::pair<Vertex, char_t>, Vertex PAIR_HASH(Vertex, char_t) > goto_t;
		typedef MAP<Vertex, Vertex> failure_t;

		typedef std::list<string_t> pattern_list;
		typedef typename pattern_list::const_iterator pattern_cont_iter;

		class ac_constructor : public default_bfs_visitor
		{
		public:
			ac_constructor(aho_corasick& ac) : ac_(ac) {}

			template <typename Edge, typename Graph>
			void examine_edge(Edge e, const Graph& g) const
			{
				typename graph_traits<Graph>::vertex_descriptor u = source(e, g);
				if (u == ac_.root_) return;

				typename graph_traits<Graph>::vertex_descriptor v = target(e, g);

				char_t a = ac_.pattern_char_[e];
				Vertex q = ac_.fail_func(u);

				while (ac_.goto_func(q, a) == ac_.null_vertex_) 
					q = ac_.fail_func(q);

				Vertex fail_v = ac_.goto_func(q, a);
				ac_.set_fail_func(v, fail_v);

				out_list_t& out_v = ac_.out_[v]; 
				const out_list_t& out_fail_v = ac_.out_[fail_v]; 
				out_v.insert(out_v.begin(), out_fail_v.begin(), out_fail_v.end());
			}

		private:
			aho_corasick& ac_;
		};

		aho_corasick()
			: null_vertex_(graph_traits<Graph>::null_vertex())
		{}
		aho_corasick(const pattern_list& patterns)
			: null_vertex_(graph_traits<Graph>::null_vertex())
			, patterns_(patterns)
		{ build(); }

		void add(const string_t& pattern) { patterns_.push_back( pattern ); }

		template<class InputIterator>
		void add(InputIterator first, InputIterator last) { patterns_.push_back(string_t(first, last)); }

		void build() throw(std::length_error);

		// result type
		typedef std::list<std::pair<size_t, out_list_t> > result_list_t;
		typedef typename result_list_t::const_iterator result_cont_iter;

		template<class InputIterator>
		result_list_t search(InputIterator beg, InputIterator end) const;

		template<class InputIterator1, class InputIterator2, class OuputIterator>
		OuputIterator replace(InputIterator1 beg, InputIterator1 end, InputIterator2 rep_beg, InputIterator2 rep_end,
							  OuputIterator result, const result_list_t& searched) const;

		// aux functions
		result_list_t search(const string_t& text) const { return search(text.begin(), text.end()); }
		string_t replace(const string_t& text, const string_t& repl) const { return replace(text, repl, search(text)); }
		string_t replace(const string_t& text, const string_t& repl, const result_list_t& searched) const
		{
			string_t result;
			result.reserve(text.length() + repl.length() * searched.size());

			replace(text.begin(), text.end(), repl.begin(), repl.end(), std::inserter(result, result.begin()), searched);
			return result;
		}

		string_t replace_bf(string_t text) const; // a brute-force

	private:
		void set_fail_func(Vertex q, Vertex r) { failure_[q] = r; }
		Vertex fail_func(Vertex q) const
		{
			if (q == root_) return root_;
			return failure_.find(q)->second;
		}

		void set_goto_func(Vertex q, char_t a, Vertex r) { goto_[std::make_pair(q, a)] = r; }
		Vertex goto_func(Vertex q, char_t a) const;

	private:
		pattern_list patterns_;

		Graph g_;
		Vertex root_;
		Vertex null_vertex_;

		char_map_t pattern_char_;
		out_map_t out_;

		goto_t goto_;
		failure_t failure_;
};

#undef MAP
#undef PAIR_HASH

#include "aho_corasick_impl.h"

#endif
